package main

import "fmt"

/*
 一般采用的都是递归的方式
先从切片中找出一个标准，然后遍历该数组，比他大的放一边，比他小的放一边，相等的就挨着
然后递归下去
时间复杂度  O(nlgn)
*/
func quickSort(arr []int) []int {
	if len(arr) <= 1 {
		return arr
	}

	low := make([]int, 0, 0)
	high := make([]int, 0, 0)
	mid := make([]int, 0, 0)
	cur := arr[0]
	for i := 0; i < len(arr); i++ {
		if cur > arr[i] {
			low = append(low, arr[i])
		} else if cur < arr[i] {
			high = append(high, arr[i])
		} else {
			mid = append(mid, arr[i])
		}
	}

	low, high = quickSort(low), quickSort(high)
	r := append(append(low, mid...), high...)
	return r
}
func main() {
	arr := []int{1, 9, 10, 30, 2, 5, 45, 8, 63, 234, 12}
	fmt.Println(quickSort(arr))
}
